package com.aqie.medium.recursion;

import com.aqie.easy.structure.TreeNode;

import java.util.*;

/**
 * 894
 * 国外：满二叉树是一类二叉树，其中每个结点恰好有 0 或 2 个子结点
 * 国内：除最后一层无任何子节点外，每一层上的所有结点都有两个子结点的二叉树。
 */
public class AllPossibleFBT {
    /**
     * 递归
     */
    Map<Integer, List<TreeNode>> memo = new HashMap<>();
    public List<TreeNode> allPossibleFBT(int N) {
        if (!memo.containsKey(N)){
            List<TreeNode> ans = new LinkedList<>();
            if (N == 1){
                ans.add(new TreeNode(0));
            }else if (N % 2 == 1){
                for (int x = 0; x < N; ++x){
                    int y = N - 1 - x;
                    for (TreeNode left : allPossibleFBT(x)){
                       for (TreeNode right : allPossibleFBT(y)){
                          TreeNode bns = new TreeNode(0);
                          bns.left = left;
                          bns.right = right;
                          ans.add(bns);
                       }
                    }
                }
            }
            memo.put(N, ans);
        }
        return memo.get(N);
    }

    /**
     * 动态规划
     * @param N
     * @return
     */
    public List<TreeNode> allPossibleFBT2(int N) {
        List<TreeNode> n1 = new ArrayList<>();
        if (N % 2 == 0) return n1;
        n1.add(new TreeNode(0));
        if (N == 1) return n1;

        int len = (N + 1) / 2;
        List<TreeNode>[] dp = new List[len];
        dp[0] = n1;

        for (int total = 3; total <= N; total += 2){
            List<TreeNode> nodes = new LinkedList<>();
            for (int leftCount = 1; leftCount < total; leftCount += 2){
                List<TreeNode> leftNodes = dp[leftCount / 2];
                List<TreeNode> rightNodes = dp[(total - leftCount - 1) / 2];

                for (TreeNode left : leftNodes){
                    for (TreeNode right : rightNodes){
                        TreeNode root = new TreeNode(0);
                        root.left = left;
                        root.right = right;
                        nodes.add(root);
                    }
                }
            }
            dp[total/2] = nodes;
        }
        return dp[len - 1];
    }
}
